package com.clstu.tree;

/**
 * 演示模拟二叉树以及二叉树的 前中后序遍历
 */
public class BinaryTreeDemo {
    public static int count1 = 0;
    public static int count2 = 0;
    public static int count3 = 0;
    public static void main(String[] args) {
        //测试
        //创建二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的节点
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        //插入节点
        binaryTree.setRoot(node1);
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        //遍历
        System.out.println("前序遍历:");
        binaryTree.preOrder();
        System.out.println("中序遍历:");
        binaryTree.infixOrder();
        System.out.println("后序遍历:");
        binaryTree.postOrder();

        //查找
        int id = 4;
        System.out.println("前序查找:");
        System.out.println(binaryTree.preFindById(id));
        System.out.println("中序查找:");
        System.out.println(binaryTree.infixFindById(id));
        System.out.println("后序查找:");
        System.out.println(binaryTree.postFindById(id));

        //删除
        System.out.println("删除前,前序遍历:");
        binaryTree.preOrder();
        binaryTree.deleteById2(3);
        System.out.println("删除后,前序遍历:");
        binaryTree.preOrder();
    }
}

/**
 * HeroNode节点类
 */
class HeroNode{
    private int id ;
    private String name;
    private HeroNode left;
    private HeroNode right;

    //构造器
    public HeroNode(int id,String name){
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    //编写方法实现前序遍历,从自己开始
    public void preOrder(){
        //前序遍历:
        // 自己 ---> 左递归 ---> 右递归
        //自己
        System.out.println(toString());
        //左递归
        if(left!=null) {
            left.preOrder();
        }
        //右递归
        if(right!=null) {
            right.preOrder();
        }
    }

    //编写方法实现中序遍历
    public void infixOrder(){
        //中序遍历:
        // 左递归 ---> 自己 ----> 右递归
        //左递归
        if(left!=null){
            left.infixOrder();
        }
        //自己
        System.out.println(toString());
        //右递归
        if (right!=null){
            right.infixOrder();
        }
    }

    //编写方法实现后续遍历
    public void postOrder(){
        //后序遍历:
        // 左递归 ---> 右递归 ---> 自己
        //左递归
        if(left!=null){
            left.postOrder();
        }
        //右递归
        if(right!=null){
            right.postOrder();
        }
        //自己
        System.out.println(toString());
    }

    //编写方法实现前序遍历查找
    public HeroNode preFindById(int id){
        System.out.println("前序查找第"+(++BinaryTreeDemo.count1)+"次");
        //前序遍历
        //自己  ---> 左查找 ----> 右查找
        //自己
        if(this.id == id){
            return this;
        }
        HeroNode resNode;//用于返回
        //左查找
        if(left!=null){
            resNode = left.preFindById(id);
            if(resNode != null){
                return resNode;
            }
        }
        //右查找
        if(right!=null){
            resNode = right.preFindById(id);
            if(resNode!=null){
                return resNode;
            }
        }
        //没找到
        return null;
    }

    //编写方法实现中序遍历查找
    public HeroNode infixFindById(int id){
        System.out.println("中序查找第"+(++BinaryTreeDemo.count2)+"次");
        //中序遍历
        // 左查找 ---> 自己 -----> 右查找
        HeroNode resNode;
        //左查找
        if(left!=null){
            resNode = left.infixFindById(id);
            if(resNode != null){
                return resNode;
            }
        }
        //自己
        if(this.id == id){
            return this;
        }
        //右查找
        if(right!=null){
            resNode = right.infixFindById(id);
            if(resNode!=null){
                return resNode;
            }
        }
        //没找到
        return null;
    }

    //编写方法实现后序遍历查找
    public HeroNode postFindById(int id){
        System.out.println("后序查找第"+(++BinaryTreeDemo.count3)+"次");
        //后序遍历
        // 左查找 ----> 自己 ----> 右查找
        HeroNode resNode;
        //左查找
        if(left!=null){
            resNode = left.postFindById(id);
            if(resNode!=null){
                return resNode;
            }
        }
        //右查找
        if(right!=null){
            resNode = right.postFindById(id);
            if(resNode!=null){
                return resNode;
            }
        }
        //自己
        if(this.id == id){
            return this;
        }
        //没找到
        return null;
    }

    //编写方法实现二叉树的删除,成功返回true,失败返回false(简陋版本,如果找到直接置空,很有可能直接删掉子树)
    public boolean deleteById(int id){
        //思路分析:
        //因为数跟单链表一样,是单向的,不能自我删除,所以要在父节点上删除子节点
        //过程:
        //1.判断左节点,如果是,删除,返回true
        //2.判断右节点,如果是,删除,返回true
        //3.左递归删除
        //4.右递归删除
        //5.如果都没有找到,返回false
        //判断左节点
        if(left!=null) {
            if (left.getId() == id) {
                left = null;
                return true;
            }
        }
        //判断右节点
        if(right!=null) {
            if (right.getId() == id) {
                right = null;
                return true;
            }
        }
        //左递归
        if(left!=null){
            if(left.deleteById(id)){
                return true;
            }
        }
        //右递归
        if(right!=null){
            if(right.deleteById(id)){
                return true;
            }
        }
        //如果都没有删除成功
        return false;
    }

    //删除升级版,(如果被删除的节点右左子节点就用左子节点代替自己,否则右子节点代替自己)
    public boolean deleteById2(int id){
        //判断左边
        if(left!=null) {
            if (left.getId() == id) {
                //左子树代替
                if (left.left != null) {
                    left = left.left;
                    return true;
                }
                //否则就是右子树代替
                left = left.right;
                return true;
            }
        }
        //判断右边
        if(right!=null) {
            if (right.getId() == id) {
                //左子树代替
                if (right.left != null) {
                    right = right.right;
                    return true;
                }
                //否则就是右子树代替
                right = right.right;
                return true;
            }
        }
        //左递归
        if(left!=null){
            if(left.deleteById2(id)){
                return true;
            }
        }
        //右递归
        if(right!=null){
            if(right.deleteById2(id)){
                return true;
            }
        }
        //如果都没有成功
        return false;
    }
}

/**
 * 二叉树类
 */
class BinaryTree{
    private HeroNode root ;

    public HeroNode getRoot() {
        return root;
    }

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //编写方法前序遍历该二叉树
    public void preOrder(){
        //如果树为空
        if(root==null){
            System.out.println("当前二叉树为空");
            return;
        }
        root.preOrder();
    }

    //编写方法中序遍历
    public void infixOrder(){
        if(root==null){
            System.out.println("当前二叉树空");
            return;
        }
        root.infixOrder();
    }

    //编写方法后续遍历二叉树
    public void postOrder(){
        if(root==null){
            System.out.println("当前二叉树空");
            return;
        }
        root.postOrder();
    }

    //前序查找
    public HeroNode preFindById(int id){
        //先判断是否树空
        if(root==null){
            return null;
        }
        return root.preFindById(id);
    }

    //中序查找
    public HeroNode infixFindById(int id){
        //是否树空
        if(root==null){
            return null;
        }
        return root.infixFindById(id);
    }

    //后续查找
    public HeroNode postFindById(int id){
        //是否树空
        if(root == null){
            return null;
        }
        return root.postFindById(id);
    }

    //删除(删除子树版)
    public boolean deleteById(int id){
        //先判断是否链表空
        if(root==null){
            return false;
        }
        //如果要删除的就是根节点
        if(root.getId()==id){
            root = null;
            return true;
        }
        //递归删除
        return root.deleteById(id);
    }

    //删除,升级版,可以保留一边,不完全删除子树
    public boolean deleteById2(int id){
        //先判断是否数空
        if(root == null){
            return false;
        }
        //如果要删除的是根节点
        if(root.getId() == id){
            //左边代替
            if(root.getLeft()!= null){
                root = root.getLeft();
                return true;
            }
            //否则右边代替
            root = root.getRight();
            return true;
        }
        //递归删除
        return root.deleteById2(id);
    }
}